#pragma once
#include <iostream>
#include <vector>
#include <utility>
#include <cassert>
#define MNODE 3
template <class K, class V, size_t M = MNODE>
struct BtreeNode
{
public:
    BtreeNode()
        :_n(M-1)
    {
        _data.resize(M, std::pair<K, V>());
        _ptr.resize(M + 1, nullptr);
    }

public:
    size_t _n;                               // 节点中的关键字个数
    std::vector<std::pair<K, V>> _data;      // 关键字存储数组
    std::vector<BtreeNode<K, V> *> _ptr;     // 孩子指针存储数组
};
template <class K, class V, size_t M = MNODE>
class Btree
{
    typedef BtreeNode<K, V, MNODE> Node;
public:
    Btree()
    {

    }
    // 插入节点
    bool Insert(std::pair<K,V> val)
    {
        // 根节点为空，说明是第一次插入，直接插入即可
        if(_root == nullptr)
        {
            Node *newnode = new Node;
            newnode->_data.push_back(val);
        }
        // 先查找,如果不存在，再插入，如果存在，则不插入
        std::pair<int, std::pair<Node *, bool>> ret = Find(val.first);
        if(!ret.second.second)
        {
            for (size_t i = ret.first; i + 1 < ret.second.first->_data.size();i++)
            {
                ret.second.first->_data[i + 1] = ret.second.first->_data[i];
            }
        }
    }
    // 查找节点
    std::pair<int,std::pair<Node *,bool>> Find(K key)
    {
        assert(_root != nullptr);
        Node *cur = _root;
        Node *parent = nullptr;
        size_t i = 0;
        while (cur)
        {
            i = 0;
            for (; i < cur->_data.size(); i++)
            {
                if (cur->_data[i].first < key && cur->_data[i+1].first > key)
                {
                    parent = cur;
                    cur = cur->_ptr[i + 1];
                    break;
                }
                if(cur->_data[i].first > key)
                {
                    parent = cur;
                    cur = cur->_ptr[i];
                    break;
                }
                if(cur->_data[i].first == key)
                    return std::make_pair(-1, std::make_pair(nullptr, true));
            }
        }
        return std::make_pair(i + 1, std::make_pair(parent, false));
    }

private:
    Node *_root = nullptr;
};
